图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图(Graph)是表示物件与物件之间的关系的数学对象，是图论的基本研究对象。一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为。

对于一个拥有n个顶点的无向连通图，它的边数一定多于n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这n-1条边(弧）组成的图被称为原无向图的生成树。

二元组的定义

图G是一个有序二元组(VE)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。E的元素都是二元组，用(x,y)表示，其中x,y∈V。

三元组的定义

图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I称为关联函数，将E中的每一个元素映射到V×V。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u, v则称作e的端点，u,v此时关于e相邻。同时，若两条边ij有一个公共顶点u，则称i,j关于u相邻。

有/无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反

边没有方向的图为无向图。

单图

一个图如果任意两顶点之间只有一条边（在有向图中为两顶点之间每个方向只有一条边);边集中不含环，则称为单图。

除了一些社交网络等直观的可以表达为图的数据，很多别的数据也可以表示为图，如图片和文本。尽管有悖直觉，但通过将图像和文本视为图，可以了解更多关于它们的对称性和结构的信息，并建立一种直觉，有助于理解其他不太像网格的图数据。

一般我们认为图片是具有多个通道的矩形栅格，以数组（array）的形式来表示。另一种方法是将图片看做有着规则结构的图，其中每个像素代表一个节点，不同节点之间通过边与相邻像素连接。每个非边界上的像素点都有8个邻居，因此存储在每个节点的信息是一个三维向量，分别对应RGB三个通道值。 一种可视化图连接性的方式是邻接矩阵（adjacency matrix）。以一张5*5的单通道图片为例，总共有5×5=25个像素，可以构造一个25×25的邻接矩阵并填充两个节点共享一条边的单元。

通过给每个字符/单词/token赋予一个数值索引，从而将文本用一串索引表示。这一方法创建了一个简单的有向图，其中每个字符/索引是一个节点（node）并通过一条边连接到后一个节点。

【实际中，并不会真的采用上述两种方式编码图片和文本。因为图片和文本都具有非常规律的结构，这样表示会带来大量的冗余：图片在其邻接矩阵中有一个带状结构，因为所有节点(像素)都连接在一个网格中。文本的邻接矩阵只是一条对角线，因为每个单词只与前一个单词连接，并连接到一个单词。】

现实中很多数据是异构结构（heterogeneously structured）的。此时，每个节点的邻居数量可能都是不同的，这样的数据很难以图以外的方式表征。现实中这样的例子有：

【深度学习中模型图是以操作作为节点，变量沿边在节点之间流动。】

图上的预测任务一般分为三种类型：图层面、节点层面和边层面。 在图层面任务，我们为整张图预测一些性质；对于节点层面的任务，我们为图中的每个节点预测一些性质；对于边层面任务，我们预测边的形式（比如是否存在）。

在图层面任务，我们预测整张图的性质。例如，对于一个分子结构图，我们可能想去预测这个分子的气味，或者它是否会与与疾病有关的受体结合。

节点级任务与预测图中每个节点的角色有关。节点级预测问题的一个典型例子是 Zach 的空手道俱乐部，预测问题是在争执之后对给定成员是否忠于 Mr. Hi 或 John H 进行分类。在这种情况下，节点与教练或管理者之间的距离与此标签高度相关。 节点层面的预测问题类比于图片分割问题，在图片分割中我们要给图片中每个像素的角色打标签。文本问题中一个相似的任务是预测句子中每个单词的词性（例如名词、动词、副词等）。

边层面推理的一个例子是图片场景理解。除了识别图片中的物体，深度学习模型还可以被用于预测它们之间的关系。我们可以将这一任务看做一个边层面的分类任务：给定代表图片中物体的节点，我们希望预测哪些节点共享一条边或者这条边的值是多少。如果我们想发现实体之间的联系，我们可以将图看做全部相互连接的，然后基于预测的结果来对图进行修剪以获得一个稀疏的图。

图结构数据是由节点和边组成的数据。节点可以表示为个体、实体或概念，边可以表示为这些节点之间的关系。例如，社交网络、化学分子、知识图谱等都可以用图结构数据进行表示。

邻居聚合是图神经网络中的基本操作之一，它通过将节点的邻居节点的信息聚合起来，以更新节点的表示。聚合方式可以是平均值、最大值、加权和等。

首要问题是思考如何让图的表示与神经网络结构兼容。机器学习模型通常采用规整数组作为输入。图具有多达四种类型的信息可以用于预测：节点、边、全局上下文和连通性（connectivity）。前三种是相对直观的：比如，使用节点，我们可以通过为每个节点分配一个索引 i 并来构建一个节点特征矩阵N并将节点node_i 的特征存储到该矩阵中。虽然这些矩阵具有可变数量的例子，但它们不需任何特殊技术就能处理。 相比之下，表示图的连通性要更加复杂一些。最明显的方法是使用邻接矩阵，因为它更容易张量化。然而这一方法有一些缺点：当节点的数量特别多时，矩阵会变得很大；每个节点的连接数变化很大，通常会产生很稀疏的矩阵，浪费存储空间。 另一个问题是，有许多邻接矩阵可以编码相同的连通性（比如不同的分配node index的方式），并且不能保证这些不同的矩阵会在深度神经网络中产生相同的结果(也就是说，它们不是排列不变（permutation invariant）的)。 一个更内存友好的表达稀疏矩阵连的方法是邻接列表。邻接列表的第k项是一个元组(i,j)，代表了节点n_i和n_ j之间的边e_k。因为我们知道边的数量要远小于邻接矩阵的规模（n^2_node），这样做避免了图中不连通部分的计算和存储。

GNN的理论基础是不动点(the fixed point)理论，这里的不动点理论专指巴拿赫不动点定理(Banach's Fixed Point Theorem)。

巴拿赫不动点定理

定义

巴拿赫不动点定理，又称为压缩映射定理或压缩映射原理，是度量空间理论的一个重要工具。它保证了度量空间的一定自映射的不动点的存在性和唯一性，并提供了求出这些不动点的构造性方法。这个定理是以斯特凡·巴拿赫命名的，他在1922年提出了这个定理。

定理内容

设(X,d)为非空的完备度量空间。设T：X→X为X上的一个压缩映射，即，存在一个非负的实数q